#define DISTANCE 0.7

#include "clusterizator.h"

#include "news_factory.h"

#include <math.h>
#include <map>
#include <iostream>

float Clusterizator::str_dist(string &src, string &dst)
{
	// В этой функции рассчитывает расстояние Левенштейна
	// и делится на длину большей строки
	if (src.size() == 0 && dst.size() == 0)
		return 0;
	if (src.size() == 0)
		return dst.size();
	if (dst.size() == 0)
		return src.size();

	vector< vector< unsigned > > matrix;
	matrix.resize(src.size()+1);
	for(unsigned i=0; i<src.size()+1; ++i)
	{
		matrix[i].resize(dst.size()+1);
		matrix[i][0] = i;
	}
	for(unsigned i=0; i<dst.size()+1; ++i)
		matrix[0][i] = i;

	unsigned top, left, top_left, price;
	for(unsigned i=1; i<src.size()+1; ++i)
	{
		for(unsigned j=1; j<dst.size()+1; ++j)
		{
			top = matrix[i][j-1];
			left = matrix[i-1][j];
			top_left = matrix[i-1][j-1];
			price = src[i-1] == dst[j-1] ? 0 : 1;
			matrix[i][j] = min ( min(top+1, left+1), top_left+price);
		}
	}

	unsigned dist = matrix[src.size()][dst.size()];
	return (float)dist/max(src.size(), dst.size());
}

string Clusterizator::isWordInSet(string &word)
{
	for (set<string>::iterator i=words.begin(); i!=words.end(); ++i)
	{
		string t_word = *i;
		if ( str_dist(word, t_word)>0.75 )
			return *i;
	}
	return "";
}

float Clusterizator::distance(NewsEntry *entry1, NewsEntry *entry2)
{
	map<string, int> *words1 = entry1->getWords();
	map<string, int> *words2 = entry2->getWords();

	set<string> all_words;
	for (map<string, int>::iterator i=words1->begin(); i!=words1->end(); ++i)
	{
		pair<string, int> value = *i;
		string word = isWordInSet(value.first);
		if (word=="")
		{
			all_words.insert(value.first);
		}
		else
		{
			(*words1)[word] += (*words1)[value.first];
		}
	}
	for (map<string, int>::iterator i=words2->begin(); i!=words2->end(); ++i)
	{
		pair<string, int> value = *i;
		string word = isWordInSet(value.first);
		if (word=="")
		{
			all_words.insert(value.first);
		}
		else
		{
			(*words2)[word] += (*words2)[value.first];
		}
	}

	//for(set<string>::iterator i=all_words.begin(); i!=all_words.end(); ++i)
		//cout << *i << endl;

	int alike_counter = 0;
	map<string, int>::iterator i;
	for (map<string, int>::iterator i=words1->begin(); i!=words1->end(); ++i)
	{
		pair<string, int> word = *i;
		if (words2->find(word.first) != words2->end())
		{
			alike_counter += (*words1)[word.first]+(*words2)[word.first];
		}
	}

	return 1-1.0*alike_counter/all_words.size();
}

vector<vector<NewsEntry*> > Clusterizator::getClusters(vector<string> &urls)
{
	for(unsigned i=0; i<entries.size(); ++i)
		delete entries[i];
	entries.clear();
	vector<vector<NewsEntry*> > clasters;
	NewsFactory factory;

	float claster_distance = DISTANCE;

	for (unsigned i=0; i<urls.size(); ++i)
	{
		cout << "start downloading article #" << i << endl;
		try
		{
			entries.push_back(factory.getNewsEntry(urls[i].c_str()));
		}
		catch (...)
		{
			cout << "error while downloading news article!" << endl;
		}
		cout << "downloading completed!" << endl;

		// мы получили статью - теперь рассчитаем расстояние от нее до всех прочих
		float min_dist = claster_distance;
		int min_dist_pos = -1;
		for (unsigned x=0; x<entries.size()-1; ++x)
		{
			float dist = distance(entries.back(), entries[x]);
			cout << "distance: " << dist << endl;
			if (dist<min_dist)
			{
				min_dist = dist;
				min_dist_pos = x;
			}
		}

		cout << "distance is " << min_dist << endl;

		// если min_dist_pos==-1 значит, что этот элемент - новый кластер
		if (min_dist_pos == -1)
		{
			cout << "its a new claster" << endl;
			clasters.push_back(vector<NewsEntry*>());
			clasters.back().push_back(entries.back());
		}
		// иначе определяем его в уже существующий кластер
		else
		{
			cout << "its an old claster" << endl;
			// для этого надо понять, в какой же кластер =)
			for (unsigned c_num=0; c_num<clasters.size(); ++c_num)
			{
				for (unsigned x=0; x<clasters[c_num].size(); ++x)
				{
					if (clasters[c_num][x] == entries[min_dist_pos])
					{
						cout << "found in " << x << endl;
						clasters[c_num].push_back(entries.back());
						break;
					}
				}
			}
		}
	}
	return clasters;
}

Clusterizator::~Clusterizator()
{
	for(unsigned i=0; i<entries.size(); ++i)
			delete entries[i];
}

/*
// Рассчет коэффициента Пирсона, не используется, потому что
// результаты оказываются хуже, чем для моей фукнции рассчета расстояния
// возможно, где-то алгоритмический баг, но я его не вижу
float Clusterizator::distancePirson(NewsEntry *entry1, NewsEntry *entry2)
{
	map<string, int> *words1 = entry1->getWords();
	map<string, int> *words2 = entry2->getWords();

	set<string> all_words;
	for (map<string, int>::iterator i=words1->begin(); i!=words1->end(); ++i)
	{
		pair<string, int> value = *i;
		string word = isWordInSet(value.first, all_words);
		if (word=="")
		{
			all_words.insert(value.first);
		}
		else
		{
			(*words1)[word] += (*words1)[value.first];
		}
	}
	for (map<string, int>::iterator i=words2->begin(); i!=words2->end(); ++i)
		{
			pair<string, int> value = *i;
			string word = isWordInSet(value.first, all_words);
			if (word=="")
			{
				all_words.insert(value.first);
			}
			else
			{
				(*words2)[word] += (*words2)[value.first];
			}
		}

	int sum1 = 0, sum2 = 0;
	int sum1sq = 0, sum2sq = 0;
	int mSum = 0;
	for(set<string>::iterator i=all_words.begin(); i!=all_words.end(); ++i)
	{
		sum1 += (*words1)[*i];
		sum2 += (*words2)[*i];
		sum1sq += pow((*words1)[*i],2);
		sum2sq += pow((*words2)[*i],2);
		mSum += ((*words1)[*i])*((*words2)[*i]);
	}

	int n=all_words.size();
	double num = mSum-(sum1*sum2/n);
	double den = sqrt( (sum1sq-pow(sum1,2)/n) * (sum2sq-pow(sum2,2)/n) );

	if (den<=0) return 0;

	return num/den;
}*/
